/*
提交链接：https://leetcode.cn/problems/kth-missing-positive-number/description/
1539. 第 k 个缺失的正整数
赖德檀 2024/9/17
*/
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        if (arr[0] > k) {
            return k;
        }

        int l = 0, r = arr.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            int x = mid < arr.size() ? arr[mid] : INT_MAX;
            if (x - mid - 1 >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
//第k个缺失的数-(最小位置之前的那个数所缺失的个数)+最小位置前面的那个数
// 5-(7-3-1)+7=第五个缺失的数-7前面有缺失的数+7
        return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1];
    }
};
